#ifndef _CSINGLELINKEDLIST_H_
#define _CSINGLELINKEDLIST_H_

/**
 *******************************************************************************
 * @brief    single linked list with c++
 * @author                
 * @since 
 *
 *******************************************************************************/

template<typename TData> struct CNode
{
	CNode() : itsData(TData()), itsNextNode(NULL)
	{
	}

	TData itsData;
	CNode<TData>* itsNextNode;
};

template<typename TData> class CList
{
public:
	CList();
	explicit CList(const TData& value);
	~CList();
	inline bool empty() const { return 0 == itsNodeCount; }
	inline unsigned int size() const { return itsNodeCount; }
	void push_back(const TData& value);
	void insert(unsigned int position, const TData& value);
	void remove(const TData& value);

private:
	CNode<TData>* itsNodeHead;
	unsigned int itsNodeCount;
};

template<typename TData>
CList<TData>::CList() : itsNodeHead(NULL), itsNodeCount(0)
{
}

template<typename TData>
CList<TData>::CList(const TData& value) : itsNodeHead(NULL), itsNodeCount(0)
{
	insert(itsNodeCount, value);
}

template<typename TData>
CList<TData>::~CList()
{
	CNode<TData>* tempNode = NULL;
	for(unsigned int pos = 0; pos < itsNodeCount; ++pos)
	{
		tempNode = itsNodeHead->itsNextNode;
		if(NULL != itsNodeHead)
		{
			delete itsNodeHead;
		}
		itsNodeHead = tempNode;
	}
}

/**
 * push_back - insert one data at the end of list
 * @value:	the data to be inserted
 */
template<typename TData>
void CList<TData>::push_back(const TData& value)
{
	insert(itsNodeCount, value);
}

/**
 * insert - insert one data into list
 * @position:  the position to be inserted; 0: before head node; 1: after head node
 * @value:	the data to be inserted
 */
template<typename TData>
void CList<TData>::insert(unsigned int position, const TData& value)
{
	// insert position is invalide
	if(position < 0 || position > itsNodeCount)
	{
		return;
	}

	// build new node
	CNode<TData>* newNode = new CNode<TData>();
	newNode->itsData = value;

	// insert head node
	if(NULL == itsNodeHead || 0 == itsNodeCount)
	{
		newNode->itsNextNode = NULL;
		itsNodeHead = newNode;
	}
	else
	{
		if(0 == position)
		{
			newNode->itsNextNode = itsNodeHead;
			itsNodeHead = newNode;
		}
		else
		{
			CNode<TData>* tempNode = itsNodeHead;
			for(unsigned int pos = 0; pos < position - 1; ++pos)
			{
				tempNode = tempNode->itsNextNode;
			}
			tempNode->itsNextNode = newNode;
		}
	}
	++itsNodeCount;
}

template<typename TData>
void CList<TData>::remove(const TData& value)
{
	// if list is empty, return directly
	if(empty())
	{
		return;
	}

	CNode<TData>* nodeToBeRemoved = NULL;

	// head node need to be removed
	if(value == itsNodeHead->itsData)
	{
		nodeToBeRemoved = itsNodeHead;
		itsNodeHead = itsNodeHead->itsNextNode;
		delete nodeToBeRemoved;
		--itsNodeCount;
	}
	else
	{
		CNode<TData>* currentNode = itsNodeHead;
		CNode<TData>* previousNode = NULL;
		CNode<TData>* nextNode = NULL;
		for(unsigned int pos = 0; pos < itsNodeCount; ++pos)
		{
			if(NULL != currentNode && value == currentNode->itsData)
			{
				previousNode = currentNode;
				currentNode = currentNode->itsNextNode;
				nextNode = currentNode->itsNextNode;

				nodeToBeRemoved = currentNode;
				previousNode->itsNextNode = nextNode;
				delete nodeToBeRemoved;
				--itsNodeCount;

				// reassign pointer, for currentNode has been deleted and invalid
				currentNode = nextNode;
			}
		}
	}
}

#endif  // _CSINGLELINKEDLIST_H_